#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
    string _numStr[10] = { "", "","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
public:
    void Combine(const string& digits, int i, vector<string>& vCombin, string combinStr)
    {
        if (i == digits.size())
        {
            vCombin.push_back(combinStr);
            return;
        }

        int num = digits[i] - '0';
        //i -> 0 -> 2 -> "abc"
        //i -> 1 -> 3 -> "def"
        //i -> 2 -> 4 -> "ghi"
        string str = _numStr[num];
        for (auto ch : str)
        {
            Combine(digits, i + 1, vCombin, combinStr + ch);
        }
    }


    vector<string> letterCombinations(string digits) 
    {
        vector<string> vCombine;
        string str;
        size_t i = 0;
        
        Combine(digits, i, vCombine, str);
        return vCombine;
    }
};

int main()
{
    Solution sl;
    vector<string> ret = sl.letterCombinations("234");
    for (auto str : ret)
    {
        cout << str << " ";
    }
    cout << endl;

	return 0;
}

